国防科技大学 编译原理 第13讲 语法分析——自下而上分析4

课程主页：

https://www.icourse163.org/course/NUDT-1003101005?tid=1460976445

这次回顾第13讲：语法分析——自下而上分析4。

第13讲 更强的$LR$分析

一个非$LR(0)$文法

考虑文法$G(S’)$：

$$\begin{aligned} (0)& \mathrm S′→\mathrm E\\ (1)& \mathrm{E} \rightarrow \mathrm{E}+\mathrm{T}\\ (2)& \mathrm{E} \rightarrow \mathrm{T}\\ (3)& \mathrm{T} \rightarrow \mathrm{T}^{*} \mathrm{F}\\ (4)& \mathrm{T} \rightarrow \mathrm{F}\\ (5)& \mathrm{F} \rightarrow(\mathrm{E})\\ (6)& \mathrm{F} \rightarrow \mathrm i \end{aligned}$$

该文法的识别活前缀的DFA以及$LR(0)$项目集规范族如下：

$I_1,I_2$和$I_9$都含有“移进－归约”冲突：

但实际上，我们可以通过其他信息来判断移进规约，回顾Follow集合：

$$\text {FOLLOW}(A)=\left\lbrace a \mid \mathrm{S} \Rightarrow \ldots A a \ldots, a \in V_{T}\right\rbrace$$

计算可得：

$$\begin{aligned} \text {FOLLOW}\left(S^{\prime}\right)&=\lbrace \sharp\rbrace \\ \text {FOLLOW}(E)&=\lbrace +,), \sharp\rbrace \end{aligned}$$

对于状态$I_1$，如果当前的单词是$\sharp$，那么使用规约；如果是$+$，那么使用移进。

$SLR(1)$冲突解决办法

冲突解决办法

• 假定一个$LR(0)$规范族含有如下的一个项目集(状态)

  $$I＝\lbrace X→α•bβ,A→α•,B→α•\rbrace$$

• $\text{FOLLOW}(A)$和$\text{FOLLOW}(B)$的交集为$\varnothing$，且不包含$b$

• 当状态$I$面临任何输入符号$a$时，可以：

  • 若$a=b$，则移进；
  • 若$a∈\mathrm{FOLLOW}(A)$，用产生式$A→α$进行归约；
  • 若$a∈\mathrm{FOLLOW}(B)$，用产生式$B→α$进行归约；
  • 此外，报错。

$SLR(1)$冲突解决办法

对之前的方法进行推广：

• 假定$LR(0)$规范族的一个项目集

  $$I= \lbrace {A}_{1} \rightarrow \alpha \cdot {a}_{1} \beta_{1}, {A}_{2} \rightarrow \alpha \cdot {a}_{2} \beta_{2}, \ldots, {A}_{ {m} } \rightarrow \alpha \cdot {a}_{ {m} } \beta_{ {m} }, \\ {B}_{1} \rightarrow \alpha_{\bullet}, {B}_{2} \rightarrow \alpha_{\bullet}, \ldots ,{B}_{n} \rightarrow \alpha_{\bullet} \rbrace$$

  如果集合

  $$\left\lbrace a_{1}, \ldots, a_{m}\right\rbrace , \text {FOLLOW}\left(B_{1}\right), \ldots, \text {FOLLOW}\left(B_{n}\right)$$

  两两不相交(包括不得有两个$\text{FOLLOW}$集合有$\sharp$)，则当状态I面临任何输入符号$a$ 时：

  • 若$a$是某个$a_i,i=1,2,…,m$，则移进；
  • 若$a∈\mathrm{FOLLOW}(B_i),i=1,2,…,n$，则用产生式$B_i→α$进行归约；
  • 此外，报错。

• 这种方法被称为$SLR(1)$解决办法，其中：S-Simple，1-最多向前看一个单词

$SLR(1)$分析表的构造

构造SLR(1)分析表的方法

• 把$G$拓广为$G′$
• 对$G′$构造
  • $LR(0)$项目集规范族$C$
  • 活前缀识别自动机的状态转换函数$GO$
• 使用$C$和$GO$，构造$SLR$分析表
  • 令每个项目集$I_k$的下标$k$作为分析器的状态，包含项目$S′→•S$的集合$I_k$的下标$k$为分析器的初态。
  • 构造分析表的$\mathrm{ACTION}$和$\mathrm{GOTO}$子表

$SLR(1)$分析表的$\text{ACTION}$和$\text{GOTO}$子表构造

算法流程：

1. 若项目$A→α•aβ$属于$I_k$且$\mathrm{GO}(I_k,a)=I_j$，$a$为终结符，则置$\mathrm{ACTION}[k,a]$为$s_j$；
2. 若项目$A→α•$属于$I_k$，那么，对任何终结符$a∈\mathrm{FOLLOW}(A)$，置$\mathrm{ACTION}[k,a]$为$r_j$；其中，假定
   $A→α$为文法$G′$的第$j$个产生式；
3. 若项目$S′→S•$属于$I_k$，则置$\mathrm{ACTION}[k,\sharp]$为$\mathrm{acc}$;
4. 若$\mathrm{GO}(I_k,A)＝I_j$，$A$为非终结符，则置$\mathrm{GOTO}[k,A]=j$；
5. 分析表中凡不能用规则1至4填入信息的空白格均置上“报错标志” 。

$SLR(1)$和$LR(0)$分析表构造方法的对比

$SLR(1)$文法

• 按上述方法构造出的$\mathrm{ACTION}$与$\mathrm{GOTO}$表如果不含多重入口，则称该文法为$SLR(1)$文法。
• 使用$SLR$表的分析器叫做一个$SLR$分析器。
• 每个$SLR(1)$文法都是无二义的。但也存在许多无二义文法不是$SLR(1)$的。
• $LR(0) ⊂ SLR(1) ⊂ $无二义文法

SLR(1)分析表构造示例

依然考虑之前的拓广文法$G(S’)$：

$$\begin{aligned} (0)& \mathrm S′→\mathrm E\\ (1)& \mathrm{E} \rightarrow \mathrm{E}+\mathrm{T}\\ (2)& \mathrm{E} \rightarrow \mathrm{T}\\ (3)& \mathrm{T} \rightarrow \mathrm{T}^{*} \mathrm{F}\\ (4)& \mathrm{T} \rightarrow \mathrm{F}\\ (5)& \mathrm{F} \rightarrow(\mathrm{E})\\ (6)& \mathrm{F} \rightarrow \mathrm i \end{aligned}$$

$\mathrm{ACTION}$和$\mathrm{GOTO}$子表如下：

一个非SLR(1)文法

例子

考虑文法$G(S’)$：

$$\begin{aligned} &(0)\ \mathrm{S}' \rightarrow \mathrm{S}\\ &(1)\ \mathrm{S} \rightarrow \mathrm{L}=\mathrm{R}\\ &(2)\ \mathrm{S} \rightarrow \mathrm{R}\\ &(3)\ \mathrm{L} \rightarrow{ }^{\star} \mathrm{R}\\ &(4)\ \mathrm{L} \rightarrow \mathrm{i}\\ &(5)\ \mathrm{R} \rightarrow \mathrm{L} \end{aligned}$$

识别活前缀的DFA以及$LR(0)$项目集规范族如下：

考虑状态$I_2$：

$$\text {FOLLOW}(\mathrm{R})=\lbrace \#,=\rbrace$$

这说明该文法不是$SLR(1)$。

但是注意到该文法

• 没有以“$R=$”为前缀的规范句型
• 有以“$\star R=$”为前缀的规范句型

当状态栈的栈顶为$2$时，如果符号栈栈顶为$L$，并且$L$之前没有$\star$，那么不能使用移入规约。

SLR冲突消解存在的问题

• $SLR$在方法中，如果项目集$I_i$含项目$A→α•$而且下一输入符号$a∈\mathrm{FOLLOW}(A)$，则状态$i$面临$a$时，可选用“用$A→α$归约”动作

• 但在有些情况下，当状态$i$显现于栈顶时，当前单词是$a$，栈里的活前缀$βα$未必允许把$α$归约为$A$，因为可能根本就不存在一个形如“$βAa$”的规范句型

• 在这种情况下，用“$A→α$”归约不一定合适

• 即$\mathrm {FOLLOW}$集合提供的信息太泛

LR(1)分析表的构造

构造LR(1)分析表的方法

• 把$G$拓广为$G′$
• 对$G′$构造$LR(1)$项目集规范族$C$和活前缀识别自动机的状态转换函数$\mathrm{GO}$
• 使用$C$和$\mathrm{GO}$，构造$LR(1)$分析表

$LR(k)$项目

• $LR(k)$项目：扩展$LR(0)$项目，附带有$k$个终结符

  $$[A→α•β, a_1a_2\ldots a_k]$$

  $a_1a_2\ldots a_k$称为向前搜索符串(或展望串)。

• 归约项目$[A→α•,a_1a_2…a_k]$的意义：当它所属的状态呈现在栈顶且后续的$k$个输入符号为$a_1a_2…a_k$时，才可以把栈顶上的$α$归约为$A$

• 对于任何移进或待约项目$[A→α•β, a_1a_2…a_k]$，$β≠ε$，搜索符串$a_1a_2…a_k$没有直接作用

有效项目

形式上我们说一个$LR(1)$项目$[A→α•β, a]$对于活前缀$γ$是有效的，如果存在规范推导

$${S}^{\prime} \stackrel{\star}{\Rightarrow}_{R} \delta A \omega \Rightarrow_{R} \delta \alpha \beta \omega$$

其中，

• $γ＝δα$
• $a$是$ω$的第一个符号，或者$a$为$\sharp$而$ω$为$ε$

有效项目的性质

• $[A→α•Bβ, a]$对活前缀$γ＝δα$是有效的，则对于每个形如$B→ξ$的产生式， 对任何$b∈\mathrm{FIRST}(βa)$，$[B→•ξ, b]$对$γ$也是有效的。

证明：

若项目$[A→α•Bβ, a]$对$γ＝δα$有效， 则有

$${S} \stackrel{\star}{\Rightarrow}_{R} \delta A a \Rightarrow_{R} \delta \alpha B \beta a \omega$$

因为

$$b \in \mathrm{FIRST}(\beta \mathrm{a})$$

所以

$$\beta a \omega \stackrel{\star}{\Rightarrow}_{R} b \varphi$$

若$B→ξ$是产生式，则

$${S} \stackrel{\star}{\Rightarrow}_{R} \delta \alpha B \beta a \omega \stackrel{\star}{\Rightarrow}_{R} \delta \alpha B b \varphi \Rightarrow_{R} \delta \alpha \xi b \varphi$$

因此项目$[B→•ξ, b]$对$γ＝δα$是有效的。

$LR(1)$项目集规范族

• 构造$LR(1)$项目集规范族
  • 闭包函数$\mathrm{CLOSURE}$
  • 转换函数$\mathrm{GO}$

项目集的闭包$\mathrm{CLOSURE}$

假定$I$是文法$G′$的任一项目集，定义和构造$I$的闭包$\mathrm{CLOSURE}(I)$如下：

1. $I$的任何项目都属于$\mathrm{CLOSURE}(I)$。
2. 若项目$[A→α•Bβ, a]$属于$\mathrm{CLOSURE}(I)$，$B→ξ$是一个产生式，那么，对于$\mathrm{FIRST}(βa)$中的每个终结符$b$，如果$[B→•ξ, b]$原来不在$\mathrm{CLOSURE}(I)$中，则把它加进去。
3. 重复执行步骤2，直至$\mathrm{CLOSURE}(I)$不再增大为止。

项目集的转换函数$\mathrm{GO}$

令$I$是一个项目集，$X$是一个文法符号，函数$\mathrm{GO}(I,X)$定义为：

$$\mathrm{GO}(I, X)＝\mathrm{CLOSURE}(J)$$

其中

$$J＝\lbrace 任何形如[ A→αX•β, a ]的项目 \Big| [ A→α•Xβ, a ]∈I \rbrace$$

LR(1)项目集规范族的构造算法

• BEGIN
  • $C:=\lbrace \mathrm{CLOSURE}( { [S′→•S，\sharp] } ) \rbrace $;
  • REPEAT
    • FOR $C$中每个项目集$I$和$G′$的每个符号$X$ DO
      • IF $\mathrm{GO}(I,X)$非空且不属于$C$，THEN
        • 把$\mathrm{GO}(I,X)$加入$C$中
  • UNTIL $C$不再增大
• END

$LR(1)$分析表的构造算法

• 把$G$拓广为$G′$
• 对$G′$构造$LR(1)$项目集规范族$C$和活前缀识别自动机的状态转换函数$\mathrm{GO}$
• 使用$C$和$\mathrm{GO}$，构造$LR(1)$分析表
• 令每个$I_k$的下标$k$为分析表的状态，令含有$[S′→•S,\sharp]$的$I_k$的$k$为分析器的初态
• 构造$LR(1)$分析表的$\mathrm{ACTION}$和$\mathrm{GOTO}$子表

$LR(1)$分析表的$\mathrm{ACTION}$和$\mathrm{GOTO}$子表构造

1. 若项目$[A→α•aβ, b]$属于$I_k$且$\mathrm{GO}(I_k, a)＝I_j$， $a$为终结符，则置$\mathrm{ACTION}[k, a]$为“$s_j$”。
2. 若项目$[A→α•,a]$属于$I_k$，则置$\mathrm{ACTION}[k, a]$为“$r_j$”；其中假定$A→α$为文法$G′$的第$j$个产生式。
3. 若项目$[S′→S•,\sharp]$属于$I_k$，则置$\mathrm{ACTION}[k, \sharp]$为“acc”。
4. 若$\mathrm{GO}(I_k,A)＝I_j$，则置$\mathrm{GOTO}[k, A]=j$。
5. 分析表中凡不能用规则1至4填入信息的空白栏均填上“出错标志”。

$LR(1)$和$SLR(1)$分析表构造方法的对比

$LR(1)$分析表和$LR(1)$文法

• 按上述算法构造的分析表，若不存在多重定义的入口(即，动作冲突)的情形，则称它是文法$G$的一张规范的$LR(1)$分析表。
• 具有规范的$LR(1)$分析表的文法称为一个$LR(1)$文法。
• 使用$LR(1)$分析表的分析器叫做一个规范的LR分析器。
• $LR(1)$状态比$SLR(1)$多
• $LR(0) ⊂ SLR(1) ⊂ LR(1) ⊂ $无二义文法

$LR(1)$分析表构造示例

$LR(1)$分析表的构造

考虑拓展文法$G(S’)$：

$$\begin{aligned} &(0) \mathrm{S}^{\prime} \rightarrow \mathrm{S}\\ &(1) \mathrm{S} \rightarrow \mathrm{BB}\\ &(2) \mathrm{B} \rightarrow \mathrm{aB}\\ &(3) \mathrm{B} \rightarrow \mathrm{b}\\ \end{aligned}$$

识别活前缀的DFA：

$LR(1)$分析表：

$LR(1)$分析示例

利用文法$G(S’)$：

$$\begin{aligned} &(0) \mathrm{S}^{\prime} \rightarrow \mathrm{S}\\ &(1) \mathrm{S} \rightarrow \mathrm{BB}\\ &(2) \mathrm{B} \rightarrow \mathrm{aB}\\ &(3) \mathrm{B} \rightarrow \mathrm{b}\\ \end{aligned}$$

以及$LR(1)$分析表：

分析$abab$：